
class Solution {
    public static String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();


        int[] hash1 = new int[128]; //利用数组来模拟哈希表，记录 tt 中字母出现的频率
        int kinds = 0; //记录 tt 中含有字母的种类

        for(char ch : t) {
            if(hash1[ch] == 0) {
                kinds++;
            }
            hash1[ch]++;
        }

        int[] hash2 = new int[128]; //记录 ss 中字母出现的频率
        int minlen = Integer.MAX_VALUE, begin = -1; //用来更新结果

        for(int left = 0, right = 0, count = 0; right < s.length; right++) {
            //进窗口
            char in = s[right];
            hash2[in]++;
            if(hash2[in] == hash1[in]) {
                count++;
            }

            //判断  满足条件时
            while(count == kinds) {
                //更新结果
                if(right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }

                //出窗口
                char out = s[left];
                left++;
                if(hash2[out] == hash1[out]) {
                    count--;
                }
                hash2[out]--;
            }
        }

        if(begin == -1) {
            return new String();
        }else {
            return ss.substring(begin, begin + minlen);
        }
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String ret = minWindow(s,t);
        System.out.println(ret);
    }
}